#ifndef JOSEPHUS_H
#define JOSEPHUS_H

#include <iostream>
using namespace std;

struct JosephusNode {
    int data;
    JosephusNode* next;
    JosephusNode(int val) : data(val), next(nullptr) {}
};

class JosephusCircle {
private:
    JosephusNode* head;
    JosephusNode* tail;
    int size;

public:
    JosephusCircle() : head(nullptr), tail(nullptr), size(0) {}
    
    ~JosephusCircle() {
        clear();
    }
    
    void createCircle(int n) {
        clear();
        for (int i = 1; i <= n; i++) {
            JosephusNode* newNode = new JosephusNode(i);
            if (!head) {
                head = newNode;
                tail = newNode;
                tail->next = head;
            } else {
                tail->next = newNode;
                tail = newNode;
                tail->next = head;
            }
            size++;
        }
    }
    
    void solveJosephus(int m) {
        if (size == 0) {
            cout << "约瑟夫环为空！" << endl;
            return;
        }
        
        if (m <= 0) {
            cout << "间隔数必须为正整数！" << endl;
            return;
        }
        
        cout << "约瑟夫环问题求解：" << endl;
        cout << "总人数: " << size << ", 报数间隔: " << m << endl;
        cout << "出列顺序: ";
        
        JosephusNode* current = head;
        JosephusNode* prev = tail;
        
        while (size > 1) {
            for (int i = 1; i < m; i++) {
                prev = current;
                current = current->next;
            }
            
            cout << current->data;
            if (size > 2) cout << " -> ";
            
            prev->next = current->next;
            if (current == head) {
                head = current->next;
            }
            if (current == tail) {
                tail = prev;
            }
            
            JosephusNode* toDelete = current;
            current = current->next;
            delete toDelete;
            size--;
        }
        
        cout << endl << "最后剩下的人: " << current->data << endl;
        head = current;
        tail = current;
        tail->next = head;
    }
    
    void displayCircle() {
        if (size == 0) {
            cout << "约瑟夫环为空！" << endl;
            return;
        }
        
        cout << "约瑟夫环: ";
        JosephusNode* current = head;
        do {
            cout << current->data;
            if (current->next != head) {
                cout << " -> ";
            }
            current = current->next;
        } while (current != head);
        cout << " -> ..." << endl;
    }
    
    void clear() {
        if (size == 0) return;
        
        tail->next = nullptr;
        
        JosephusNode* current = head;
        while (current) {
            JosephusNode* nextNode = current->next;
            delete current;
            current = nextNode;
        }
        
        head = nullptr;
        tail = nullptr;
        size = 0;
    }
    
    int getSize() const {
        return size;
    }
};

#endif